堆排序

堆排序是利用堆的性质来对数组进行排序，主要分为建堆和交换两个步骤

堆

堆在形式上是一棵满足一定性质的二叉树。

由于二叉树良好的形态已经包含了父节点和孩子节点的关系信息，因此就可以不需要使用链表而使用数组来存储堆。

堆分为两种，最大堆和最小堆，以最大堆为例，最大堆保持了根结点大于两个左右两个孩子，同时所有子树一次类推。例如：

int heap[]={9,8,6,7,5,3,2,1,4,0};

设父节点的编号为 i, 则其左孩子节点的编号为2*i+1, 右孩子节点的编号为2*i+2

设孩子节点的编号为i, 则其父节点的编号为(i-1)/2

堆排序

堆排序指的就是利用堆的性质对数组进行排序。

小顶堆中根节点小于两个左右子节点的性质。

将一个无序数组看做是一个完全二叉树，此时没有成堆。

建堆

将该数组进行建堆操作，

即将父节点和左右子节点三个数进行比较，最小的数作为父节点，

循环操作整颗树后，根节点就是数组中最小的树。

问题转化为将树中的最小值移动至根节点。

void buildHeap(vector<int> &arr,int unsortSize){//unsortSize表示未排序元素的个数
    int rootIndex=unsortSize/2-1;//第一个非叶子节点的下标
    for(;rootIndex>=0;rootIndex--){
        //左右节点都存在，比较三个数，最小值与根节点交换
        if(2*rootIndex+2<=unsortSize){//注意是小于未排序数列的大小，不是整个数列的大小
            if(arr[2*rootIndex+1]<arr[2*rootIndex+2]){//左节点小于右节点
                if(arr[rootIndex]>arr[2*rootIndex+1]){//左节点最小
                    swap(arr[rootIndex],arr[2*rootIndex+1]);
                }
            } else {　　　//右节点小于左节点
                if(arr[rootIndex]>arr[2*rootIndex+2]){//右节点最小
                    swap(arr[rootIndex],arr[2*rootIndex+2]);
                }
            }      
        }　else {  //右节点不存在，只比较根节点与左节点
            if(arr[rootIndex]>arr[2*rootIndex+2]){
                swap(arr[rootIndex],arr[2*rootIndex+2]);
            }
        }
    }
}

注意建堆时节点数是小于未排序数列的大小，不是整个数列的大小

交换

建堆操作后，数组中的最小值就是根节点。为了循环遍历，我们将最小值与数组最后一个数进行交换。这样，除数组最后一个数之外又变成了一个能构成完全二叉树的无序数组。

void swapHeap(vector<int> &arr,int end){
    int temp=arr[end];
    arr[end]=arr[0];
    arr[0]=temp;
}

排序

堆排序就是先建立一个小根堆，然后不断地交换堆顶最小元素，交换N-1次就OK了

void heapSort(vector<int> &arr){
    int size=arr.size();
    if(size<=1)return;
    for(int i=size;i>1;--i){//size表示未排序元素个数，当只剩一个时就退出，所以是i>1
        buildHeap(arr,i);
        swapHeap(arr,i);
    }
}

性质

时间复杂度：

• 建堆复杂度为$O(logN)$
• 交换可以忽略
• 需要进行$N-1$次建堆

所以，堆排序的时间复杂度是$O(N-1)*O(logN)=O(NlogN)$

不稳定排序

在一个长为n 的序列，堆排序的过程是从第n / 2开始和其子节点共3个值选择最大（大顶堆）或者最小（小顶堆），这3个元素之间的选择当然不会破坏稳定性。但当为n / 2 - 1， n / 2 - 2， … 1这些个父节点选择元素时，就会破坏稳定性。有可能第n / 2个父节点交换把后面一个元素交换过去了，而第n / 2 - 1个父节点把后面一个相同的元素没 有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法

参考资料